Technical Field
Embodiments described herein generally relate to processors. In particular, embodiments described herein generally relate to the use of Morton coordinates in processors.
Background Information
Computer systems and other electronic devices often utilize data that is organized in data structures. The data structures may represent particular arrangements or organizations of the data. One common type of data structure often used in computer systems is an array, such as a two-dimensional (2D) array.
FIG. 1 illustrates an example of a two-dimensional (2D) array 100 in which data items (e.g., the values 7, 16, 24, 27, etc.) are arranged in two dimensions. Representatively, the 2D data structure may represent a table, matrix, or the like. In the illustration, the two dimensions are defined by a first dimension or x-axis 102, and a second dimension or y-axis 104. The x-axis and y-axis are mutually perpendicular and define a 2D grid in which the data items are arranged. The data items in the 2D array may be identified by the values of the x and y indices or coordinates along the two axis. The x-coordinate represents the distance and/or relative position along the x-axis measured from the origin where the two axis intersect, whereas the y-coordinate represents the distance and/or relative position along the y-axis measured from the origin. In the illustrated example, the x-coordinates and the y-coordinates have the values of 0, 1, 2, and 3. Representatively, the coordinates or indices may represent row and column numbers. By way of example, the data item having the value of 14 may be identified by the x,y-coordinates (1,2) which may indicate the data item in column 2, row 3. Similarly, the data item having the value of 24 may be identified by decrementing the y-coordinate by one unit to get the x,y-coordinates (1,1). Other examples are contemplated where the 2D data structure represents a Cartesian coordinate system, and the coordinates may represent locations of points in the Cartesian coordinate system.
Within computer systems and other electronic devices, such arrays and other data structures may be stored in memory or other linear storage. Different ways are possible for storing the 2D and other multi-dimensional arrays in memory. For example, the 2D arrays may be stored in row-major order. In row-major order, the rows of the array are contiguous in the memory. For example, the data items may be stored in the memory in the order 27, 3, 8, 11, 9, 24, 7, 1, 8, 14, 16, 2, 7, 16, 4, and 20. Alternatively, the 2D arrays may be stored in the memory in column-major order. In column-major order, the columns of the array are contiguous in the memory. For example, the data items may be stored in the memory in the order 27, 9, 8, 7, 3, 24, 14, 16, 8, 7, 16, 4, 11, 1, 2, and 20.